package com.gupao.alg.alg9;

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

public class Topic3_2_102_Level_Travel {


    public static void main(String[] args) {
        BinaryTree bTree = new BinaryTree();
        bTree.root = bTree.buildTreeByArray();
        int testMethod = 4;
        List<List<Integer>> res = null;
        switch (testMethod) {
            case 1: //仅仅遍历并输出一遍，不考虑分层的问题
                List<Integer> simple = simpleLevelOrder(bTree.root);
                System.out.println(simple);
                break;
            case 2://leetcode102  不同的层的结点要分行显示
                res = level102Order(bTree.root);
                break;
            case 3://LeetCode 107 层序遍历-自底向上
                res = levelOrderBottom(bTree.root);
                break;
            case 4://LeetCode 429 二叉树的锯齿形层序遍历
                res = zigzagLevelOrder(bTree.root);
                break;
        }
        System.out.println(res);

    }

    /**
     * 简单的层次遍历：仅仅遍历并输出一遍，不考虑分层的问题
     * 应输出结果 [3, 9, 20, 15, 7]
     *
     * @param root
     * @return
     */
    public static List<Integer> simpleLevelOrder(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        LinkedList<TreeNode> linkedList = new LinkedList<>();
        linkedList.add(root);
        while (linkedList.size() > 0) {
            int size = linkedList.size();
            for (int i = 0; i < size; i++) {
                TreeNode remove = linkedList.remove();
                if(remove.left != null) {
                    linkedList.add(remove.left);
                }
                if(remove.right != null) {
                    linkedList.add(remove.right);
                }
                list.add(remove.val);
            }
        }
        return list;
    }


    /**
     * leetcode102 二叉树的层序遍历
     * 不同的层的结点要分行显示
     * 应输出结果: [[3], [9, 20], [15, 7]]
     *
     * @param root
     * @return
     */
    public static List<List<Integer>> level102Order(TreeNode root) {
        List<List<Integer>> lists = new ArrayList<>();
        LinkedList<TreeNode> linkedList = new LinkedList<>();
        linkedList.add(root);
        processData(linkedList, lists, 2);
        return lists;
    }

    /**
     * LeetCode 107 层序遍历-自底向上
     * 应输出结果 [[15, 7], [9, 20], [3]]
     *
     * @param root
     * @return
     */
    public static List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> lists = new ArrayList<>();
        LinkedList<TreeNode> linkedList = new LinkedList<>();
        linkedList.add(root);
        processData(linkedList, lists, 3);
        Collections.reverse(lists);
        return lists;
    }

    /**
     * LeetCode429 二叉树的锯齿形层序遍历
     * 输出结果为： [[3], [20, 9], [15, 7]]
     * 正  反  正
     * @param root
     * @return
     */
    public static List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> lists = new ArrayList<>();
        LinkedList<TreeNode> linkedList = new LinkedList<>();
        linkedList.add(root);
        processData(linkedList, lists, 4);
        return lists;
    }

    /**
     * 数据处理
     * @param linkedList
     * @param lists
     * @param flag 2 按层由左到右打印; 3 按层从后向前遍历; 4 锯齿打印;
     */
    public static void processData(LinkedList<TreeNode> linkedList, List<List<Integer>> lists, int flag) {
        while (linkedList.size() > 0) {
            int size = linkedList.size();
            List<Integer> list = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode remove = linkedList.remove();
                // 取反
                if (i % 2 == 0 && 4 == flag) {
                    if (remove.left != null) {
                        linkedList.add(remove.right);
                    }
                    if (remove.right != null) {
                        linkedList.add(remove.left);
                    }
                } else {
                    if(remove.left != null) {
                        linkedList.add(remove.left);
                    }
                    if(remove.right != null) {
                        linkedList.add(remove.right);
                    }
                }
                list.add(remove.val);
            }
            lists.add(list);
        }
    }
}

